#pragma once
#include <iostream>
#include <vector>

using namespace std;

namespace Su
{
	template<class K, class V>
	class HashNode
	{
	public:

		HashNode(const pair<K,V>& kv = make_pair(K(),V()))
		:_kv(kv)
		,_next(nullptr)
		{}

		typedef HashNode<K, V> Node;
	
		pair<K, V> _kv; //哈希表里每一个方格里存储的值
		Node* _next; //每一个方格都指向自己桶的下一个元素
	};
	

	

	template<class K, class V>
	class HashTable
	{
	public:
		//默认构造
		HashTable()
		{
			_table.resize(10, nullptr);
		}

		//仿函数，将不同的数转换为整数
		template<class K>
		class HashFunc
		{
		public:
			size_t operator()(const K& key)
			{
				return (size_t)key;
			}
		};

		template<>
		class HashFunc<string>
		{
		public:
			size_t operator()(const string& key)
			{
				size_t ret = 0;
				
				for (auto ch : key)
				{
					ret *= 131;
					ret += ch;
				}
				return ret;
			}
		};
		

		typedef HashNode<K, V> Node;

		//实现插入
		bool insert(const pair<K, V>& kv)
		{
			//当平衡因子为1时进行扩容 
			//注意不能用capacity，因为下面需要用[ ]遍历旧表，而[ ]只能使用size以内的值
			//对size以外capacity以内的值使用[ ] 会报错
			if (n / _table.size() >= 1)
			{
				//不能直接扩容原table，会导致映射关系出错
				//创建一个新表，遍历旧表，将每个值头插到新表里
				//注意：这里不能用insert，insert会new一个新Node，这个行为的消耗太大
				vector<Node*> newtable(_table.size() * 3, nullptr);
				for (auto& Hashi : _table)
				{
					if (Hashi)
					{
						Node* cur = Hashi;
						Node* prev = nullptr;
						while (cur)
						{
							HashFunc<K> hf;
							size_t newHashi = hf(cur->_kv.first) % newtable.size(); //找好映射关系
							prev = cur->_next;
							cur->_next = newtable[newHashi];
							newtable[newHashi] = cur;
							cur = prev;
						}
					}
				}
				_table.swap(newtable);
			}

			//1.先让数磨去table的大小，获得对应映射
			//①为了防止key的类型是string，需要使用仿函数将first转换成整数
			HashFunc<K> hf;
			size_t Hashi = hf(kv.first) % _table.size(); //找好映射关系
			//准备插入，三种情况：
			//1.对应位置为空，直接插入
			//2.对应位置不为空，进行头插
			//3.对应位置不为空且key相等，返回false
			Node* cur = _table[Hashi];
			while (cur)
			{
				//如果已经有该值，放弃插入
				if (cur->_kv.first == kv.first)
				{
					return false;
				}
				cur = cur->_next;
			}
			//走到这一步说明cur为空，即没有重复值，可以进行插入
			//①采用头插
			Node* newnode = new Node(kv);
			newnode->_next = _table[Hashi];
			_table[Hashi] = newnode;
			n++;
			return true;
		}

		bool print()
		{
			int num = 0;
			for (const auto& i : _table)
			{
				printf("[%d] ->", num++);
				Node* cur = i;
				while (cur)
				{
					cout << cur->_kv.first << "->";
					cur = cur->_next;
				}
				cout << "NULL" << endl;
			}
			cout << endl;
			return true;
		}

		pair<K,V>* find(const K& key)
		{
			HashFunc<K> fc;
			size_t Hashi = fc(key) % _table.size();
			if (_table[Hashi])
			{
				Node* cur = _table[Hashi];
				while (cur)
				{
					if (cur->_kv.first == key) return &(cur->_kv);
					cur = cur->_next;
				}
			}
			//1.该位置的桶为空 2.cur没有找到要查找的值
			return nullptr;//用空表示查找失败
		}

		bool erase(const K& key)
		{
			//pair<K,V>* ret = find(kv);
			if (find(key) == nullptr) return false;
			HashFunc<K> fc;
			size_t Hashi = fc(key) % _table.size();
			Node* cur = _table[Hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[Hashi] = cur->_next;
						delete cur;
						return true;
					}
					prev->_next = cur->_next;
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			
			return false;
		}
	private:
		vector<Node*> _table; //_table是一个指针数组，每个单元存储的是桶的地址
		size_t n = 0; //记录有效数据，当平衡因子为1（平均每个桶都有一个值）时扩容
	};
}